package com.atguigu.sort;


public class ShellSort {

    private ShellSort() {
    }

    public static <E extends Comparable<E>> void sort(E[] data) {
        int h = data.length / 2;
        while (h >= 1) {
            for (int start = 0; start < h; start++) {
                for (int i = start + h; i < data.length; i = i + h) {
                    E e = data[i];
                    int j;
                    for (j = i; j >= h && data[j - h].compareTo(e) > 0; j =j- h){
                        data[j]=data[j-h];
                    }
                    data[j]=e;
                }
            }
            h=h/2;
        }
    }
    public static <E extends Comparable<E>> void sort2(E[]data){
        int h=data.length/2;
        while(h>=1){
            for (int i = h; i < data.length; i++) {
                E e=data[i];
                int j;
                for(j=i;j>=h&&data[j].compareTo(data[j-h])<0;j-=h){
                    data[j]=data[j-h];
                }
                data[j]=e;
            }
            h=h/2;
        }
    }
    public static <E extends Comparable<E>> void sort3(E[]data){
        int h=1;
        while(h<data.length){
            h=h*3+1;
        }
        //步长序列：1,4,13,40.....
        while(h>=1){
            for (int i = 0; i < data.length; i++) {
                E e=data[i];
                int j;
                for(j=i;j>=h&&data[j].compareTo(data[j-h])<0;j-=h){
                    data[j]=data[j-h];
                }
                data[j]=e;
            }
            h=h/3;
        }

    }


}
